Union Bound

For any random events A1,...,AkA_1,...,A_k: Pr[A1A2...Ak]Pr[A1]+Pr[A2]+...+Pr[Ak]\mathrm{Pr}[A_1 \cup A_2 \cup ... \cup A_k] \leq \mathrm{Pr}[A_1] + \mathrm{Pr}[A_2] + ... + \mathrm{Pr}[A_k]

(here in Pr[A1A2...Ak]\mathrm{Pr}[A_1 \cup A_2 \cup ... \cup A_k], \cup means “or”)